﻿/** 
 * Copyright (c) 2001 University of Maryland, College Park, MD 20742, USA
 * Copyright (c) 2005 In4Arch
 *
 *  The MIT License
 *  Permission is hereby granted, free of charge, to any person obtaining a copy of this 
 *  software and associated documentation files (the "Software"), to deal in the Software 
 *  without restriction, including without limitation the rights to use, copy, modify, merge, 
 *  publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons 
 *  to whom the Software is furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be included in all copies 
 *  or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
 *  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 
 *  PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
 *  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 
 *  CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE 
 *  OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * Authors: Benjamin B. Bederson and Martin Wattenberg 2001 
 * http://www.cs.umd.edu/hcil/treemap-history/index.shtml
 * 
 * Author: moedusa moedusa@gmail.com 2005
 * http://moedusa.name/
 *
 * Author: Nikita Shlyakhov shlyakhov@mail.ru 2006
 **/
 
import in4arch.alg.treemap.AbstractMapLayout; 
import in4arch.alg.treemap.SliceLayout; 
import in4arch.alg.treemap.MapModel; 
import in4arch.alg.treemap.Rect; 

/** 
 * This layout uses a static binary tree for
 * dividing map items. It is not great with regard to
 * aspect ratios or ordering, but it has excellent
 * stability properties.
 *
 * And it does not work in Flash.
 */
class in4arch.alg.treemap.BinaryTreeLayout extends AbstractMapLayout {
	
	private var callNum:Number = 0;
	
    public function layout(model:MapModel, bounds:Rect):Void {
		var items_array:Array = model.getItems();
		_layout(items_array, 0, items_array.length-1, bounds, true)
	}
	
    public function _layout(items_array:Array, startIndex:Number, stopIndex:Number, bounds:Rect, vertical:Boolean):Void {
        if (startIndex > stopIndex) {
            throw new Error("start, end= "+startIndex+", "+stopIndex);
		}
		
        if (startIndex == stopIndex){
            items_array[startIndex].setRect(bounds);
            return;
		}
		
        var mid:Number = (startIndex+stopIndex)/2;
        var ttl:Number = _totalSize(items_array, startIndex, stopIndex);
        var fst:Number = _totalSize(items_array, startIndex, mid);
        var a:Number = fst/ttl;
		
        var x:Number = bounds.x;
		var y:Number = bounds.y;
		var w:Number = bounds.w;
		var h:Number = bounds.h;
		
        if (vertical) {
            var b1:Rect = new Rect(x,y,w*a,h);
            var b2:Rect = new Rect(x+w*a,y,w*(1-a),h);
            doCallLayout(items_array, startIndex, mid, b1, !vertical);
            doCallLayout(items_array, mid+1, stopIndex, b2, !vertical);
        } else {
            var b1:Rect = new Rect(x,y,w,h*a);
            var b2:Rect = new Rect(x,y+h*a,w,h*(1-a));
            doCallLayout(items_array, startIndex, mid, b1, !vertical);
            doCallLayout(items_array, mid+1, stopIndex, b2, !vertical);
        }
		
    }
	
	private function  doCallLayout(items_array:Array, startIndex:Number, stopIndex:Number, bounds:Rect, vertical:Boolean):Void {
		_layout(items_array, startIndex, stopIndex, bounds, vertical);
	}
    
	/*
    private function normAspect(a:Number, b:Number):Number {
        return Math.max(a/b, b/a);
    }
    
    private function sum(items:Array, start:Number, end:Number):Number {
        var s:Number = 0;
        for (var i=start; i<=end; i++){
            s += items[i].getSize();
		}
        return s;
    }
    
    private function findMax(items:Array, start:Number, end:Number):Number {
        var m:Number = 0;
        var n:Number = -1;
        for (var i=start; i<=end; i++) {
            var s:Number =items[i].getSize();
            if (s >= m) {
                m=s;
                n=i;
            }
        }
        return n;
    }
    
	*/
	
    public function getName():String {
        return "Binary Tree";
    }
    
    public function getDescription():String {
        return "Uses a static binary tree layout.";
    }
     
}